class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        path = [''] * (n * 2)

        # 目前填了 left 个左括号，right 个右括号
        def dfs(left, right):
            if right == n:
                ans.append(''.join(path))
                return
            if left < n: # 可以填左括号
                path[left + right] = '('  # 直接覆盖
                dfs(left + 1, right)
            if right < left:  # 可以填右括号
                path[left + right] = ')'
                dfs(left, right + 1)
        
        dfs(0, 0)
        return ans

